package com.dxb.test.sort;

/**
 * 堆排序
 * 堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。
 */
public class HeapSort extends BaseSort {
    public HeapSort(int[] array) {
        super(array);
    }

    private int getParentIndex(int child) {
        return (child - 1) / 2;
    }

    private int getLeftChildIndex(int parent) {
        return 2 * parent + 1;
    }

    private int getRightChildIndex(int parent) {
        return getLeftChildIndex(parent) + 1;
    }

    @Override
    public void sort() {
        int last = length - 1;
        // 将堆所有数据重新排序，使其成为最大堆
        for (int i = getParentIndex(last); i >= 0; i--) {
            adjustHeap(i, last);
        }
        // 堆调整
        while (last >= 0) {
            swap(0, last--);
            adjustHeap(0, last);
        }
    }

    /**
     * 最大堆整堆：将堆的末端子节点作调整，使得子节点永远小于父节点
     * 从i节点开始调整,len为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2
     */
    private void adjustHeap(int i, int len) {
        int left = getLeftChildIndex(i);
        while (left <= len) {
            //在左右子节点中寻找最大的
            if (left + 1 < len && array[left] < array[left + 1]) {
                left++;
            }
            // 停止筛选：最大子节点小于父节点
            if (array[i] >= array[left]) {
                break;
            }
            //swap后，父节点最大
            swap(i, left);
            i = left;
            left = getLeftChildIndex(i);
        }
    }

    public static void main(String args[]) {
        int[] array = {99, 78, 26, 17, 82, 36, 9, 81, 22, 100, 30, 20, 17, 85};
        BaseSort qs = new HeapSort(array);
        qs.run();
    }

}
